package com.gong.suanfa.heapSort;

/**
 * @author GongChang
 * @version 1.0
 * @date 2021/6/10 0010 10:04
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {9,8,7,6,5,4};
        sort(arr);
        return;
    }

    public static void sort(int[] arr){
        for (int i = arr.length - 1; i >= 0; i--) {
            heap(arr,i,arr.length-1);
        }
        swap(arr,0,arr.length-1);
        int end = arr.length-1-1;
        while (end > 0){
            heap(arr,0,end);
            swap(arr,0,end);
            end--;
        }

    }

    public static void heap(int[] arr,int start,int end){
        //判断是否有左节点
        if (start*2+1>end){
            return;
        }
        int index = start;
        //判断是否有右节点
        if ((index*2+2)>end){
            if (arr[index]<arr[index*2+1]){
                swap(arr,index,index*2+1);
            }else {
                return;
            }
        }
        //当有左节点和右节点时
        while ((index*2+2) <= end){
            int max = arr[index]>arr[index*2+1]?index:index*2+1;
            max = arr[max]>arr[index*2+2]?max:index*2+2;
            swap(arr,index,max);
            if (max == index){
                return;
            }
            index = max;
        }
    }

    private static void swap(int[] arr, int index, int i) {
        int t = arr[index];
        arr[index] = arr[i];
        arr[i] = t;
    }
}
